#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

void printArry(int* a, int n)
{
	for (size_t i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	/*int mid = begin + (end-begin) / 2;
	if (begin < mid)
	{
		_MergeSort(a, tmp, begin, mid);
	}
	if (mid + 1 < end)
	{
		_MergeSort(a, tmp, mid+1, end);
	}*/

	if (begin == end) return;
	int mid = begin + (end - begin) / 2; //(begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);

	//两个有序的数组合并为一个有序的数组
	//[begin, mid] [mid+1, end]
	int* target_tmp = tmp + begin;
	int* arr1 = a + begin;
	int* arr2 = a + mid + 1;
	while (arr1 <= a + mid && arr2 <= a + end)
	{
		if (*arr1 < *arr2)
			*(target_tmp++) = *(arr1++);
		else
			*(target_tmp++) = *(arr2++);
	}
	while (arr1 <= a + mid)
		*(target_tmp++) = *(arr1++);
	while (arr2 <= a + end)
		*(target_tmp++) = *(arr2++);

	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}


void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(1);
	}

	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(1);
	}

	int gap = 1;
	while(gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//第二组都越界不存在, 这一组就不需要归并
			if (begin2 >= n) break;

			//第二组的begin2每越界, End2越界了, 需要修正一下
			if (end2 >= n) end2 = n-1;
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
			memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		gap *= 2;
	}

	free(tmp);

}

// 计数排序
void CountSort(int* a, int n)
{
	//求出最大数组长度
	int mini = 0, maxi = 0;
	for (int i = 1; i < n; i++)
	{
		if (a[i] < a[mini])
			mini = i;
		if (a[i] > a[maxi])
			maxi = i;
	}
	int arr_len = a[maxi] - a[mini] + 1 ;

	// 创建临时数组
	int* tmp = (int*)calloc(arr_len, sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(1);
	}

	// 开始计数
	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - a[mini]]++;
	}
	//排序
	int j = 0;
	int min = a[mini];
	for (int i = 0; i < arr_len; i++)
	{
		while (tmp[i])
		{
			a[j++] = min + i;
			tmp[i]--;
		}
	}
	free(tmp);
}


void testMergeSort()
{
	int a[] = { 3, 1, 9, 4, 6, 15, 7, 12, 65, 88, 1, 0, 6, 4, 77, 12, 10, 45, 99 };
	int n = sizeof(a) / sizeof(a[0]);
	MergeSort(a, n);
	printArry(a, n);

}

testMergeSortNonR()
{
	int a[] = { 3, 1, 9, 4, 6, 15, 7, 12, 65, 88, 1, 0, 6, 4, 77, 12, 10, 45, 99 };
	int n = sizeof(a) / sizeof(a[0]);
	MergeSortNonR(a, n);
	printArry(a, n);
}

testCountSort()
{
	int a[] = { 3, 1, 9, 4, 6, 15, 7, 12, 65, 88, 1, 0, 6, 4, 77, 12, 10, 45, 99 };
	int n = sizeof(a) / sizeof(a[0]);
	CountSort(a, n);
	printArry(a, n);
}

int main()
{
	printf("\nMerge Sort:      ");
	testMergeSort();
	printf("\nMerge Sort NonR: ");
	testMergeSortNonR();
	printf("\nCount Sort:      ");
	testCountSort();
	return 0;
}


